package cn.edu.gxnu.dsa.queue;

import cn.edu.gxnu.dsa.list.Node;

public class PriorityQueue implements IQueue {
	private Node front;
	private Node rear;

	public PriorityQueue() {
		front = null;
		rear = null;
		front = rear;
	}

	@Override
	public void clear() {
		front = null;
		rear = null;
		front = rear;
	}

	@Override
	public boolean isEmpty() {
		return front == null;
	}

	@Override
	public int length() {
		Node p = front;
		int length = 0;
		while (p != null) {
			p = p.getNext();
			length++;
		}
		return length;
	}

	@Override
	public Object peek() {
		if (front == null) {
			return null;
		}
		return front.getData();
	}

	@Override
	public void enQueue(Object o) {
		PriorityData pdata = (PriorityData) o;
		Node newest = new Node(pdata);
		if (front == null) {
			front = rear = newest;
		} else {
			Node p = front;
			Node q = front;
			while (p != null && pdata.getPriority() >= ((PriorityData) p.getData()).getPriority()) {
				q = p;
				p = p.getNext();
			}
			if (p == null) {
				rear.setNext(newest);
				rear = newest;
			} else if (p == front) {
				newest.setNext(front);
				front = newest;
			} else {
				q.setNext(newest);
				newest.setNext(p);
			}
		}

	}

	@Override
	public Object deQueue() {
		if (front == null) {
			return null;
		} else {
			Node p = front;
			front = p.getNext();
			return p.getData();
		}
	}

	public void display() {
		if (!isEmpty()) {
			Node p = front;
			while (p != rear.getNext()) {
				PriorityData q = (PriorityData) p.getData();
				System.out.println(q.getElement() + "  " + q.getPriority());
				p = p.getNext();
			}
		} else {
			System.out.println("The queue is empty. Please check your algorithm!!!");
		}
	}

}
